package com.jia.leetCode;

import java.util.Stack;

public class Pro0143 {

	//快慢指针分为前后两段，后面一段reverse，然后两段进行穿插
	public void reorderList(ListNode head) {
		if(head == null || head.next == null) return;
		//快慢指针
		ListNode slow = head, fast = head;
		while(fast.next != null&& fast.next.next!=null) {
			fast= fast.next.next;
			slow = slow.next;
		}
		//后段反转
		ListNode needReverse = slow.next;
		slow.next = null;
		needReverse = reverse(needReverse);
		ListNode cur = head;
		while(cur!=null && needReverse!=null) {
			ListNode curSecond = needReverse;
			needReverse = needReverse.next;
			ListNode curNext = cur.next;
			cur.next = curSecond;
			curSecond.next = curNext;
			cur = curNext;
		}
	}
	//头插 Time:O(n) Space:O(1)
	public ListNode reverse(ListNode head) {
		ListNode dummy = new ListNode(-1);//傀儡节点
		while(head != null) {
			ListNode next = head.next;
			head.next = dummy.next;
			dummy.next = head;
			head = next;
		}
		return dummy.next;
	}

	//使用栈
	public void reorderList2(ListNode head) {
		int length = 0;
		if(head == null || head.next == null) return ;
		Stack<ListNode> s = new Stack<ListNode>();
		ListNode node = head;
		while(node != null) {
			++length;
			s.push(node);
			node = node.next;
		}
		int len = 0;
		node = head;
		while(len < length / 2) {
			ListNode nodeNext = node.next;
			node.next = s.pop();
			node.next.next = nodeNext;
			node = nodeNext;
			++len;
		}
		if(node != null) node.next = null;
	}
	class ListNode {
		public int val;
		public ListNode next;
		public ListNode(int x) {val = x;}
	}

}
